package classics.DFS;

/**
 * ex695 最大岛屿面积 DFS
 */
public class ex695 {
    static int n;
    static int m;
    public static int maxAreaOfIsland(int[][] grid) {
        if(grid.length==0){
            return 0;
        }
        m = grid.length;
        n = grid[0].length;
        int max = 0;
        int[][]used = new int[m][n];
        for(int i = 0 ;i<m;i++){
            for(int j = 0;j<n;j++){
                if(grid[i][j]==1&&used[i][j]==0){
                    max = Math.max(dfs(grid,used,i,j),max);
                }
            }
        }
        return max;
    }

    public static int dfs(int [][] grid,int[][]used,int x,int y){
        if(x<0||x>=m||y<0||y>=n||grid[x][y]==0||used[x][y]==1){
            return 0;
        }
        used[x][y]=1;
        int count=1;
        count+=dfs(grid,used,x+1,y);
        count+=dfs(grid,used,x-1,y);
        count+=dfs(grid,used,x,y+1);
        count+=dfs(grid,used,x,y-1);
        return count;
    }
    public static void main(String[] args) {
        int[][] in = {{1,1,0,0,0},{1,1,0,0,0},{0,0,0,1,1},{0,0,0,1,1}};
        int i = maxAreaOfIsland(in);
        System.out.println(i);

    }

}
